{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Beautiful Partitions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: beautifulPartitions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #完美分割的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，每个字符是数字&nbsp;<code>'1'</code>&nbsp;到&nbsp;<code>'9'</code>&nbsp;，再给你两个整数&nbsp;<code>k</code> 和&nbsp;<code>minLength</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果对 <code>s</code>&nbsp;的分割满足以下条件，那么我们认为它是一个 <strong>完美</strong>&nbsp;分割：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s</code>&nbsp;被分成 <code>k</code>&nbsp;段互不相交的子字符串。</li>\n",
    "\t<li>每个子字符串长度都 <strong>至少</strong>&nbsp;为&nbsp;<code>minLength</code>&nbsp;。</li>\n",
    "\t<li>每个子字符串的第一个字符都是一个 <b>质数</b> 数字，最后一个字符都是一个 <strong>非质数</strong>&nbsp;数字。质数数字为&nbsp;<code>'2'</code>&nbsp;，<code>'3'</code>&nbsp;，<code>'5'</code>&nbsp;和&nbsp;<code>'7'</code>&nbsp;，剩下的都是非质数数字。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <code>s</code>&nbsp;的 <strong>完美</strong>&nbsp;分割数目。由于答案可能很大，请返回答案对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后的结果。</p>\n",
    "\n",
    "<p>一个 <strong>子字符串</strong>&nbsp;是字符串中一段连续字符串序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"23542185131\", k = 3, minLength = 2\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>存在 3 种完美分割方案：\n",
    "\"2354 | 218 | 5131\"\n",
    "\"2354 | 21851 | 31\"\n",
    "\"2354218 | 51 | 31\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"23542185131\", k = 3, minLength = 3\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>存在一种完美分割方案：\"2354 | 218 | 5131\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"3312958\", k = 3, minLength = 1\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>存在一种完美分割方案：\"331 | 29 | 58\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k, minLength &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code>&nbsp;每个字符都为数字&nbsp;<code>'1'</code>&nbsp;到&nbsp;<code>'9'</code> 之一。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-beautiful-partitions](https://leetcode.cn/problems/number-of-beautiful-partitions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-beautiful-partitions](https://leetcode.cn/problems/number-of-beautiful-partitions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"23542185131\"\\n3\\n2', '\"23542185131\"\\n3\\n3', '\"3312958\"\\n3\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        L = len(s)\n",
    "        primes, other = '2357', '14689'\n",
    "        if k*minLength > L or s[0] in other or s[-1] in primes: return 0\n",
    "        last = '9'\n",
    "        pos = []\n",
    "        for i, c in enumerate(chain(s, '2')):\n",
    "            if c in primes and last in other:\n",
    "                pos.append(i)\n",
    "            last = c\n",
    "        LP = len(pos)\n",
    "        l = LP - 2\n",
    "        while l >= 0 and pos[-1] - pos[l] < minLength:\n",
    "            l -= 1\n",
    "        if l < 0: return 0\n",
    "        accu = [0]*LP\n",
    "        accu[0] = 1\n",
    "        M = 10**9+7\n",
    "        for _ in range(k):\n",
    "            _l = l\n",
    "            lastAccu = 0\n",
    "            for r in range(LP-1, -1, -1):\n",
    "                # pos[_l] <= pos[r] - minLength\n",
    "                _l = bisect_right(pos, pos[r]- minLength, 0, _l+1) - 1\n",
    "                lastAccu = accu[r] = (lastAccu + (accu[0] - accu[_l+1] if _l >= 0 else 0)) % M\n",
    "        return accu[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        # S[i][n] = sum(S[i-k][n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        primes = ['2', '3', '5', '7']\n",
    "\n",
    "        if s[0] not in primes or s[-1] in primes:\n",
    "            return 0\n",
    "\n",
    "        breakPts = [i for i in range(minLength, len(s)-minLength+1) if s[i] in primes and s[i-1] not in primes]\n",
    "        nearest = [0] * len(breakPts)\n",
    "        for i in range(len(nearest)):\n",
    "            flag = False\n",
    "            for j in range(i-1, max(-1, i-(minLength+1)//2-1), -1):\n",
    "                if breakPts[i] - breakPts[j] >= minLength:\n",
    "                    nearest[i] = j\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                nearest[i] = -1\n",
    "\n",
    "        # select k - 1 points out of breakPts\n",
    "        # print('breakPts:', breakPts)\n",
    "        # print('nearest:', nearest)\n",
    "\n",
    "        if len(breakPts) < k - 1:\n",
    "            return 0\n",
    "\n",
    "        dp = [[1] * len(breakPts) for _ in range(2)] # dp with space optimization\n",
    "        for i in range(2, k):\n",
    "            cur = i % 2\n",
    "            prev = 1 - cur\n",
    "            for j in range(i-1):\n",
    "                dp[cur][j] = 0\n",
    "            dp[cur][i-1] = sum(dp[prev][i-2:nearest[i-1]+1])\n",
    "            for j in range(i, len(breakPts)-(k-1-i)):\n",
    "                dp[cur][j] = dp[cur][j-1] + sum(dp[prev][nearest[j-1]+1:nearest[j]+1])\n",
    "            # print('i:', i, dp[cur])\n",
    "        cur = (k - 1) % 2\n",
    "        # print('cur:', cur, 'k - 2:', k-2)\n",
    "        ans = sum(dp[cur][k-2:]) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int,l: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def is_prime(c: str) -> bool:\n",
    "            return c in \"2357\"\n",
    "       \n",
    "        def can_partition(j: int) -> bool:\n",
    "            return j == 0 or j == n or not is_prime(s[j - 1]) and is_prime(s[j])\n",
    "\n",
    "        n = len(s)\n",
    "        if k * l > n or not is_prime(s[0]) or is_prime(s[-1]):  \n",
    "            return 0\n",
    "        f = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            sum = 0\n",
    "            for j in range(i * l, n - (k - i) * l + 1):\n",
    "                if can_partition(j - l): sum = (sum + f[i - 1][j - l]) % MOD \n",
    "                if can_partition(j): f[i][j] = sum\n",
    "        return f[k][n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, l: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def is_prime(c: str) -> bool:\n",
    "            return c in \"2357\"\n",
    "        # 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）\n",
    "        def can_partition(j: int) -> bool:\n",
    "            return j == 0 or j == n or not is_prime(s[j - 1]) and is_prime(s[j])\n",
    "\n",
    "        n = len(s)\n",
    "        if k * l > n or not is_prime(s[0]) or is_prime(s[-1]):  # 剪枝\n",
    "            return 0\n",
    "        f = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            sum = 0\n",
    "            # 优化：枚举的起点和终点需要给前后的子串预留出足够的长度\n",
    "            for j in range(i * l, n - (k - i) * l + 1):\n",
    "                if can_partition(j - l): sum = (sum + f[i - 1][j - l]) % MOD  # j'=j-l 双指针\n",
    "                if can_partition(j): f[i][j] = sum\n",
    "        return f[k][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, l: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def is_prime(c: str) -> bool:\n",
    "            return c in \"2357\"\n",
    "        # 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）\n",
    "        def can_partition(j: int) -> bool:\n",
    "            return j == 0 or j == n or not is_prime(s[j - 1]) and is_prime(s[j])\n",
    "\n",
    "        n = len(s)\n",
    "        if k * l > n or not is_prime(s[0]) or is_prime(s[-1]):  # 剪枝\n",
    "            return 0\n",
    "        f = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            sum = 0\n",
    "            # 优化：枚举的起点和终点需要给前后的子串预留出足够的长度\n",
    "            for j in range(i * l, n - (k - i) * l + 1):\n",
    "                if can_partition(j - l): sum = (sum + f[i - 1][j - l]) % MOD  # j'=j-l 双指针\n",
    "                if can_partition(j): f[i][j] = sum\n",
    "        return f[k][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "\n",
    "        n  =len(s)\n",
    "\n",
    "        mod =10**9+7\n",
    "        def is_prime(c:str)->bool:\n",
    "            return c in \"2357\"\n",
    "\n",
    "        def can_partition(j:int)->bool:\n",
    "            return j == 0 or j ==n  or not is_prime(s[j-1]) and is_prime(s[j])\n",
    "\n",
    "\n",
    "        if k *minLength >n or not is_prime(s[0]) or is_prime(s[-1]):\n",
    "            return 0\n",
    "\n",
    "        \n",
    "        f= [[0]*(n+1) for _ in range(k+1)]\n",
    "\n",
    "        f[0][0] = 1\n",
    "\n",
    "        for i in range(1,k+1):\n",
    "            sum = 0\n",
    "            for j in range(i*minLength,n-(k-i)*minLength+1):\n",
    "                if can_partition(j-minLength):\n",
    "                    sum = (sum +f[i-1][j-minLength])%mod\n",
    "                if can_partition(j):\n",
    "                    f[i][j] =sum\n",
    "\n",
    "        return f[k][n]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        # 这一道题可直接dp\n",
    "        n = len(s)\n",
    "        mod = 10 ** 9 + 7\n",
    "        def isPrime(char):\n",
    "            return char in \"2357\"\n",
    "        \n",
    "        # 判断能否在这个点能分割（开头结尾也算在内）\n",
    "        def canPartition(j):\n",
    "            return j == 0 or j == n or not isPrime(s[j - 1]) and isPrime(s[j])\n",
    "        \n",
    "        if k * minLength > n or not isPrime(s[0]) or isPrime(s[-1]):\n",
    "            return 0\n",
    "        \n",
    "        # 构建二维数组，a[i][j]表示将s的前j个字符分割成i段的方案数\n",
    "        a = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "        a[0][0] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            sum = 0\n",
    "            for j in range(i * minLength, n + 1 - minLength * (k - i)):\n",
    "                # 对于每一个在范围中的j，往前找能分割的点并加入到sum当中\n",
    "                if canPartition(j - minLength):\n",
    "                    sum += a[i - 1][j - minLength]\n",
    "                # 将sum赋值给二维数组a[i][j]\n",
    "                if canPartition(j):\n",
    "                    a[i][j] = sum % mod\n",
    "        \n",
    "        return a[k][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        n = len(s)\n",
    "        def is_prime(c:str)->bool:\n",
    "            return c in \"2357\"\n",
    "        def canSplit(j:int)->bool:\n",
    "            return j==0 or j==n or (not is_prime(s[j-1]) and is_prime(s[j]))\n",
    "        \n",
    "        if k*minLength>n or not is_prime(s[0]) or is_prime(s[-1]):\n",
    "            return 0\n",
    "        dp = [[0]*(n+1) for _ in range(k+1)]\n",
    "        dp[0][0]=1\n",
    "        for i in range(1,k+1):\n",
    "            sums=0\n",
    "            for j in range(i*minLength,n-(k-i)*minLength+1):\n",
    "                if canSplit(j-minLength): sums = (sums+dp[i-1][j-minLength])%mod \n",
    "                if canSplit(j): dp[i][j] = sums\n",
    "        return dp[k][n]\n",
    "\n",
    "\n",
    "        return dp(0,k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, l: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        \n",
    "        def is_prime(c:str)-> bool:\n",
    "            return c in \"2357\"\n",
    "\n",
    "        def can_partition(j:int)-> bool: # 判断是否可以在j-1 和 j之间分割\n",
    "            return j == 0 or j == n or not is_prime(s[j - 1]) and is_prime(s[j])\n",
    "        n = len(s)\n",
    "        if k * l > n or not is_prime(s[0]) or is_prime(s[-1]):\n",
    "            return 0\n",
    "        f = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            sum = 0\n",
    "            for j in range(i * l, n - (k - i) * l + 1): # 优化： 枚举的起点和终点需要给前后的子串预留出足够的长度\n",
    "                if can_partition(j - l): sum = (sum + f[i - 1][j - l]) % mod\n",
    "                if can_partition(j): f[i][j] = sum\n",
    "        return f[k][n]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, m: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        def is_prime(c):\n",
    "            return c in '2357'\n",
    "        n = len(s)\n",
    "        if k*m > n or is_prime(s[-1]) or not is_prime(s[0]):\n",
    "            return 0\n",
    "        \n",
    "        def can_part(i):\n",
    "            return i == 0 or i == n or not is_prime(s[i - 1]) and is_prime(s[i])\n",
    "\n",
    "\n",
    "        # f[i][j] 前j个字符分成i个的方案数,答案是f[k][n]\n",
    "        f = [[0]*(n + 1) for _ in range(k + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1,k + 1):\n",
    "            pre_s = 0\n",
    "            for j in range(i*m,n - (k - i)*m + 1):\n",
    "                # j是切割的开始位置，j-1是前一段最后\n",
    "                if can_part(j - m):\n",
    "                    pre_s += f[i - 1][j - m]\n",
    "                    pre_s %= MOD\n",
    "                if can_part(j):\n",
    "                    f[i][j] = pre_s\n",
    "        return f[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, l: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def is_prime(c: str) -> bool:\n",
    "            return c in \"2357\"\n",
    "        # 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）\n",
    "        def can_partition(j: int) -> bool:\n",
    "            return j == 0 or j == n or not is_prime(s[j - 1]) and is_prime(s[j])\n",
    "\n",
    "        n = len(s)\n",
    "        if k * l > n or not is_prime(s[0]) or is_prime(s[-1]):  # 剪枝\n",
    "            return 0\n",
    "        f = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            sum = 0\n",
    "            # 优化：枚举的起点和终点需要给前后的子串预留出足够的长度\n",
    "            for j in range(i * l, n - (k - i) * l + 1):\n",
    "                if can_partition(j - l): sum = (sum + f[i - 1][j - l]) % MOD  # j'=j-l 双指针\n",
    "                if can_partition(j): f[i][j] = sum\n",
    "        return f[k][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, l: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def is_prime(c: str) -> bool:\n",
    "            return c in \"2357\"\n",
    "        # 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）\n",
    "        def can_partition(j: int) -> bool:\n",
    "            return j == 0 or j == n or not is_prime(s[j - 1]) and is_prime(s[j])\n",
    "\n",
    "        n = len(s)\n",
    "        if k * l > n or not is_prime(s[0]) or is_prime(s[-1]):  # 剪枝\n",
    "            return 0\n",
    "        f = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            sum = 0\n",
    "            # 优化：枚举的起点和终点需要给前后的子串预留出足够的长度\n",
    "            for j in range(i * l, n - (k - i) * l + 1):\n",
    "                if can_partition(j - l): sum = (sum + f[i - 1][j - l]) % MOD  # j'=j-l 双指针\n",
    "                if can_partition(j): f[i][j] = sum\n",
    "        return f[k][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        def isprime(c):\n",
    "            return c in \"2357\"\n",
    "        \n",
    "        def can_partition(j):\n",
    "            return j==0 or j==n or not isprime(s[j-1]) and isprime(s[j])\n",
    "        \n",
    "        n=len(s)\n",
    "        if k*minLength>n or not isprime(s[0]) or isprime(s[-1]):\n",
    "            return 0\n",
    "        f=[[0]*(n+1) for _ in range(k+1)]\n",
    "        f[0][0]=1\n",
    "        for i in range(1,k+1):\n",
    "            sum=0\n",
    "            for j in range(i*minLength,n-(k-i)*minLength+1):\n",
    "                if can_partition(j-minLength):sum=(sum+f[i-1][j-minLength])%MOD\n",
    "                if can_partition(j):f[i][j]=sum\n",
    "        return f[k][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, l: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def is_prime(c: str) -> bool:\n",
    "            return c in \"2357\"\n",
    "        # 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）\n",
    "        def can_partition(j: int) -> bool:\n",
    "            return j == 0 or j == n or not is_prime(s[j - 1]) and is_prime(s[j])\n",
    "\n",
    "        n = len(s)\n",
    "        if k * l > n or not is_prime(s[0]) or is_prime(s[-1]):  # 剪枝\n",
    "            return 0\n",
    "        f = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            sum = 0\n",
    "            # 优化：枚举的起点和终点需要给前后的子串预留出足够的长度\n",
    "            for j in range(i * l, n - (k - i) * l + 1):\n",
    "                if can_partition(j - l): sum = (sum + f[i - 1][j - l]) % MOD  # j'=j-l 双指针\n",
    "                if can_partition(j): f[i][j] = sum\n",
    "        return f[k][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, l: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def is_prime(c: str) -> bool:\n",
    "            return c in \"2357\"\n",
    "        # 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）\n",
    "        def can_partition(j: int) -> bool:\n",
    "            return j == 0 or j == n or not is_prime(s[j - 1]) and is_prime(s[j])\n",
    "\n",
    "        n = len(s)\n",
    "        if k * l > n or not is_prime(s[0]) or is_prime(s[-1]):  # 剪枝\n",
    "            return 0\n",
    "        f = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, k + 1):\n",
    "            sum = 0\n",
    "            # 优化：枚举的起点和终点需要给前后的子串预留出足够的长度\n",
    "            for j in range(i * l, n - (k - i) * l + 1):\n",
    "                if can_partition(j - l): sum = (sum + f[i - 1][j - l]) % MOD  # j'=j-l 双指针\n",
    "                if can_partition(j): f[i][j] = sum\n",
    "        return f[k][n]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def beautifulPartitions(self, s: str, k: int, l: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        def is_prime(c: str) -> bool:\n",
    "\n",
    "            return c in \"2357\"\n",
    "\n",
    "        # 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）\n",
    "\n",
    "        def can_partition(j: int) -> bool:\n",
    "\n",
    "            return j == 0 or j == n or not is_prime(s[j - 1]) and is_prime(s[j])\n",
    "\n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        if k * l > n or not is_prime(s[0]) or is_prime(s[-1]):  # 剪枝\n",
    "\n",
    "            return 0\n",
    "\n",
    "        f = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "\n",
    "        f[0][0] = 1\n",
    "\n",
    "        for i in range(1, k + 1):\n",
    "\n",
    "            sum = 0\n",
    "\n",
    "            # 优化：枚举的起点和终点需要给前后的子串预留出足够的长度\n",
    "\n",
    "            for j in range(i * l, n - (k - i) * l + 1):\n",
    "\n",
    "                sum = (sum + f[i - 1][j - l]) % MOD  # j'=j-l 双指针\n",
    "\n",
    "                if can_partition(j): f[i][j] = sum\n",
    "\n",
    "        return f[k][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, l: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def is_prime(c: str) -> bool:\n",
    "            return c in \"2357\"\n",
    "        # 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）\n",
    "        def can_partition(j: int) -> bool:\n",
    "            return j == 0 or j == n or not is_prime(s[j - 1]) and is_prime(s[j])\n",
    "\n",
    "        n = len(s)\n",
    "        if k * l > n or not is_prime(s[0]) or is_prime(s[-1]):  # 剪枝\n",
    "            return 0\n",
    "\n",
    "        f = [[0] * (n + 1) for _ in range(k + 1)]\n",
    "        f[0][0] = 1\n",
    "\n",
    "        for i in range(1, k+1):\n",
    "            tot = 0\n",
    "            for j in range(i*l, n-(k-i)*l+1): # 循环优化枚举的奇点和终点，需要给前后的子串流出足够的长度\n",
    "                if can_partition(j-l):\n",
    "                    tot = (tot + f[i-1][j-l]) % MOD\n",
    "                if can_partition(j):\n",
    "                    f[i][j] = tot\n",
    "        return f[k][n] \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 +7\n",
    "P = {'2','3','5','7'}\n",
    "NP = {'1','4','6','8','9'}\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, mL: int) -> int:\n",
    "        n = len(s)\n",
    "        if s[0] not in P or s[-1] not in NP:return 0\n",
    "        Ppos = [0]\n",
    "        for idx in range(1,n):\n",
    "            i = s[idx]\n",
    "            if i in P and s[idx-1] in NP:Ppos.append(idx)\n",
    "        Ppos.append(n)\n",
    "        F = [[0] * (k+1) for i in range(len(Ppos))]\n",
    "        for i in range(1,len(Ppos)):\n",
    "            if Ppos[i] >= mL:F[i][1] = 1\n",
    "                \n",
    "        for i in range(2,k+1):\n",
    "            s,pos = 0,0\n",
    "            for j in range(1,len(Ppos)):\n",
    "                while Ppos[j] - mL >= Ppos[pos]:\n",
    "                    s += F[pos][i-1]\n",
    "                    s %= MOD\n",
    "                    pos += 1\n",
    "                F[j][i] = s\n",
    "                F[j][i] %= MOD\n",
    "        return F[-1][-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "思考dp\n",
    "将长为j的字符串s，分成i段\n",
    "\n",
    "最后一步：\n",
    "分割出一个字串\n",
    "长度为x\n",
    "且x是s的后缀\n",
    "\n",
    "去掉最后一步\n",
    "长为j-x的字符串，分成i-1段\n",
    "\n",
    "f[i][j] 表示把长为j的字符串分成i段的合法方案数,j也代表第i段的终止位置\n",
    "f[i][j]+=f[i-1][j']  j'是第i-1段的结束下标\n",
    "        枚举j'\n",
    "        s[j']为质数，s[j'-1]不是质数\n",
    "        s[j]是质数,s[j-1]不是质数\n",
    "        j-j'>=minL\n",
    "\n",
    "优化dp：用前缀和tot替代枚举\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, l: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        n=len(s)\n",
    "        def is_prime(x:int)->bool:\n",
    "            return x in '2357'\n",
    "        if not is_prime(s[0]) or is_prime(s[-1]) or k*l>n:\n",
    "            return 0\n",
    "        f=[[0]*(n+1) for _ in range(k+1)]\n",
    "        f[0][0]=1\n",
    "        #存在下标越界问题的，都一定要特判\n",
    "        def can_partiion(j:int)->bool:\n",
    "            return j == 0 or j == n or not is_prime(s[j - 1]) and is_prime(s[j])\n",
    "        for i in range(1,k+1):\n",
    "            tot=0\n",
    "            for j in range(i*l,n+1):#可以保证每个可能的分割位置不重不漏\n",
    "                if can_partiion(j-l):tot=(tot+f[i-1][j-l])%MOD\n",
    "                if can_partiion(j):f[i][j]=tot\n",
    "        return f[k][n]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, m: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        n = len(s)\n",
    "\n",
    "        f = [[0]*(n + 1) for _ in range(k + 1)]\n",
    "        # f[i][j] 代表前j个字符里切成i份的方案\n",
    "        f[0][0] = 1\n",
    "        def is_prime(j):\n",
    "            return s[j] in '2357'\n",
    "\n",
    "        def can_part(j):\n",
    "            # j 从0到n\n",
    "            return j == 0 or j == n or is_prime(j) and not is_prime(j - 1)\n",
    "\n",
    "        \n",
    "        if not is_prime(0) or is_prime(n - 1) or k*m > n:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(1,k + 1):\n",
    "            pre_s = 0 # 前缀和优化\n",
    "            for j in range(i*m,n - (k - i)*m + 1):\n",
    "                # 枚举的是开始位置，j - 1是上一段结束位置\n",
    "                if can_part(j - m):\n",
    "                    pre_s = (pre_s + f[i - 1][j - m])% MOD\n",
    "                if can_part(j):\n",
    "                    f[i][j] = pre_s\n",
    "        return f[k][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, m: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        ps = \"2357\"\n",
    "        if k * m > n or s[0] not in ps or s[-1] in ps:\n",
    "            return 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, k + 1):\n",
    "            su = 0\n",
    "            for j in range(i * m, n + 1):\n",
    "                # print(i, j, su)\n",
    "                if j - m == 0 or (s[j - m - 1] not in ps and s[j - m] in ps):\n",
    "                    su = (su + dp[j - m][i - 1]) % mod\n",
    "                if j == n or (s[j - 1] not in ps and s[j] in ps):\n",
    "                    dp[j][i] = su\n",
    "        # for i in range(n):\n",
    "        #     print(dp[i])\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        if s[-1] in ['2','3','5','7'] or s[0] not in ['2','3','5','7']:\n",
    "            return 0\n",
    "        lst=[]\n",
    "        n=len(s)\n",
    "        for i in range(minLength-1,n-1):\n",
    "            if s[i] not in ['2','3','5','7'] and s[i+1] in ['2','3','5','7']:\n",
    "                lst.append(i)\n",
    "    \n",
    "        lst.append(n-1)\n",
    "        dp=[[0]*len(lst) for i in range(k+1)]  #dp[i][j]  第i段到第j个字符结束的种数\n",
    "        #求dp[k][n-1]\n",
    "        #initialize\n",
    "        for i in range(len(lst)):\n",
    "            dp[1][i]=1\n",
    "        for part in range(2,k+1):\n",
    "            res=0\n",
    "            p=0\n",
    "            for i, j in enumerate(lst):\n",
    "                while j-lst[p]>=minLength:\n",
    "                    res+=dp[part-1][p]\n",
    "                    p+=1\n",
    "                dp[part][i]=res\n",
    "        return dp[k][-1]%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        mod=10**9+7\n",
    "        ls1=['2','3','5','7']\n",
    "        n=len(s)\n",
    "        if s[0] not in ls1 or s[-1] in ls1:\n",
    "            return 0\n",
    "        indexls=[]\n",
    "        for i in range(1,n-1):\n",
    "\n",
    "            if s[i] not in ls1 and s[i+1] in ls1:\n",
    "                indexls.append(i)\n",
    "        indexls.append(n-1)\n",
    "        m=len(indexls)\n",
    "        #print(indexls)\n",
    "        prels=[[0 for i in range(k)] for j in range(m)]\n",
    "        dpls=[[0 for i in range(k)] for j in range(m)]\n",
    "        for i in range(m):\n",
    "            if indexls[i]+1>=minLength:\n",
    "                dpls[i][0]=1\n",
    "            prels[i][0]=prels[i-1][0]+dpls[i][0]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,min(i+1,k)):\n",
    "                for l in range(i,-1,-1):\n",
    "                    if indexls[l]<=indexls[i]-minLength:\n",
    "                        dpls[i][j]=prels[l][j-1]\n",
    "\n",
    "                        break\n",
    "                prels[i][j]=(prels[i-1][j]+dpls[i][j])%mod\n",
    "        #print(dpls)\n",
    "        #print(prels)\n",
    "        return dpls[-1][-1]%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        ls1 = ['2', '3', '5', '7']\n",
    "        n = len(s)\n",
    "        if s[0] not in ls1 or s[-1] in ls1:\n",
    "            return 0\n",
    "        indexls = []\n",
    "        for i in range(1, n - 1):\n",
    "            if s[i] not in ls1 and s[i + 1] in ls1:\n",
    "                indexls.append(i)\n",
    "        indexls.append(n - 1)\n",
    "        m = len(indexls)\n",
    "        # print(indexls)\n",
    "        prels = [[0 for i in range(k)] for j in range(m)]\n",
    "        dpls = [[0 for i in range(k)] for j in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            if indexls[i] + 1 >= minLength:\n",
    "                dpls[i][0] = 1\n",
    "            prels[i][0] = prels[i - 1][0] + dpls[i][0]\n",
    "        index=-1\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, min(i + 1, k)):\n",
    "                while indexls[index+1]<=indexls[i]-minLength:\n",
    "                    index+=1\n",
    "                if index>-1:\n",
    "                    dpls[i][j] = prels[index][j - 1]\n",
    "                prels[i][j] = (prels[i - 1][j] + dpls[i][j]) % mod\n",
    "\n",
    "        return dpls[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        ls1 = ['2', '3', '5', '7']\n",
    "        n = len(s)\n",
    "        if s[0] not in ls1 or s[-1] in ls1:\n",
    "            return 0\n",
    "        indexls = []\n",
    "        for i in range(1, n - 1):\n",
    "            if s[i] not in ls1 and s[i + 1] in ls1:\n",
    "                indexls.append(i)\n",
    "        indexls.append(n - 1)\n",
    "        m = len(indexls)\n",
    "        # print(indexls)\n",
    "        prels = [[0 for i in range(k)] for j in range(m)]\n",
    "        dpls = [[0 for i in range(k)] for j in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            if indexls[i] + 1 >= minLength:\n",
    "                dpls[i][0] = 1\n",
    "            prels[i][0] = prels[i - 1][0] + dpls[i][0]\n",
    "        index=-1\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, min(i + 1, k)):\n",
    "                while indexls[index+1]<=indexls[i]-minLength:\n",
    "                    index+=1\n",
    "                if index>-1:\n",
    "                    dpls[i][j] = prels[index][j - 1]\n",
    "                prels[i][j] = (prels[i - 1][j] + dpls[i][j]) % mod\n",
    "        # print(dpls)\n",
    "        # print(prels)\n",
    "        return dpls[-1][-1] % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        ls1 = ['2', '3', '5', '7']\n",
    "        n = len(s)\n",
    "        if s[0] not in ls1 or s[-1] in ls1:\n",
    "            return 0\n",
    "        indexls = []\n",
    "        for i in range(1, n - 1):\n",
    "\n",
    "            if s[i] not in ls1 and s[i + 1] in ls1:\n",
    "                indexls.append(i)\n",
    "        indexls.append(n - 1)\n",
    "        m = len(indexls)\n",
    "        # print(indexls)\n",
    "        def bs(num):\n",
    "            if num<indexls[0]:\n",
    "                return -1\n",
    "            l=0\n",
    "            r=m\n",
    "            while l<=r:\n",
    "                mid=(l+r)//2\n",
    "                if indexls[mid]<=num and indexls[mid+1]>num:\n",
    "                    return mid\n",
    "                elif indexls[mid]<num:\n",
    "                    l=mid\n",
    "                elif indexls[mid]>=num:\n",
    "                    r=mid\n",
    "\n",
    "\n",
    "        prels = [[0 for i in range(k)] for j in range(m)]\n",
    "        dpls = [[0 for i in range(k)] for j in range(m)]\n",
    "        for i in range(m):\n",
    "            if indexls[i] + 1 >= minLength:\n",
    "                dpls[i][0] = 1\n",
    "            prels[i][0] = prels[i - 1][0] + dpls[i][0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, min(i + 1, k)):\n",
    "                l=bs(indexls[i]-minLength)\n",
    "                if l>-1:\n",
    "                    dpls[i][j] = prels[l][j - 1]\n",
    "\n",
    "\n",
    "                prels[i][j] = (prels[i - 1][j] + dpls[i][j]) % mod\n",
    "        # print(dpls)\n",
    "        # print(prels)\n",
    "        return dpls[-1][-1] % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = '2357'\n",
    "MOD = int(1e9) + 7\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        # 若开头和结尾不符合条件则无法分割\n",
    "        if s[0] not in primes or s[-1] in primes: return 0\n",
    "        L = len(s)\n",
    "        idxs = []\n",
    "        # 将所有能用的分割点找出来\n",
    "        for i, a, b in zip(range(1, L - 1), s[1:-1], s[0:-2]):\n",
    "            # 即当前数字是质数且前一位不是质数\n",
    "            if a in primes and b not in primes:\n",
    "                idxs.append(i)\n",
    "        \n",
    "        \n",
    "        # idx: 起始位置  sur: 剩余要分割的子字符串数量\n",
    "        # dfs函数的含义就是：返回s[idx:]分割成sur个长度至少minLength的子字符串的方案数\n",
    "        @cache\n",
    "        def dfs(idx, sur):\n",
    "            # 当分割数量为1时，当前剩余字符串就是1个，返回1\n",
    "            if sur == 1: return 1\n",
    "            i = idx + minLength\n",
    "            # 找到最靠近idx的分割点\n",
    "            start = bisect_left(idxs, i)\n",
    "            ans = 0\n",
    "            # 枚举可用的分割点\n",
    "            for i in idxs[start:]:\n",
    "                # 剪枝，当剩余字符不够分割时直接退出\n",
    "                if L - i < (sur - 1) * minLength: break\n",
    "                # 累加可行的分割方案\n",
    "                ans += dfs(i, sur - 1)\n",
    "            return ans % MOD\n",
    "        \n",
    "        ans = dfs(0, k)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        prim = \"2357\"\n",
    "        n = len(s)\n",
    "        mod = 10**9+7\n",
    "        dp = [[0]*(k+1) for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            if s[i] in prim and s[-1] not in prim: dp[i][1] = 1\n",
    "        for t in range(2,k+1):\n",
    "            sm = 0\n",
    "            indx = n-t*minLength\n",
    "            i = min(n, indx+minLength)\n",
    "            while indx >= 0:\n",
    "                if i < n and s[i] in prim and i>0 and not s[i-1] in prim: sm += dp[i][t-1]\n",
    "                if s[indx] in prim: dp[indx][t] += sm\n",
    "                i-=1\n",
    "                indx-=1\n",
    "        return dp[0][k]%mod\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        prime_index = [i for i in range(len(s)) if s[i] in '2357']\n",
    "        n, m = len(prime_index), len(s)\n",
    "        if len(prime_index) < k or prime_index[0] != 0 or prime_index[-1] == m-1:\n",
    "            return 0\n",
    "        @cache\n",
    "        def dfs(i: int, c: int) ->int:\n",
    "            l = prime_index[i]\n",
    "            if c == 0:\n",
    "                return 1 if m-l >= minLength else 0\n",
    "            cnt = 0\n",
    "            for j in range(i+1, n-c+1):\n",
    "                r = prime_index[j]\n",
    "                if m-r < c*minLength:\n",
    "                    break\n",
    "                if r - l < minLength or prime_index[j-1] == r-1:\n",
    "                    continue\n",
    "                cnt += dfs(j, c-1)\n",
    "            return cnt%MOD\n",
    "        return dfs(0, k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        prime_index = [i for i in range(len(s)) if s[i] in '2357']\n",
    "        n, m = len(prime_index), len(s)\n",
    "        if len(prime_index) < k or prime_index[0] != 0:\n",
    "            return 0\n",
    "        @cache\n",
    "        def dfs(i: int, c: int) ->int:\n",
    "            l = prime_index[i]\n",
    "            if c == 0:\n",
    "                if m-l >= minLength and prime_index[-1] != m-1:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            cnt = 0\n",
    "            for j in range(i+1, n-c+1):\n",
    "                r = prime_index[j]\n",
    "                if m-r < c*minLength:\n",
    "                    break\n",
    "                if r - l < minLength or prime_index[j-1] == r-1:\n",
    "                    continue\n",
    "                cnt += dfs(j, c-1)\n",
    "            return cnt%MOD\n",
    "        return dfs(0, k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, kk: int, minLength: int) -> int:\n",
    "        if s[0] not in '2357' or s[-1] in '2357':\n",
    "            return 0\n",
    "        \n",
    "        m = len(s)\n",
    "        poss = [0]\n",
    "        for i in range(1, m):\n",
    "            if s[i] in '2357' and s[i-1] not in '2357':\n",
    "                poss.append(i)\n",
    "\n",
    "        # print(poss)\n",
    "\n",
    "        n = len(poss)\n",
    "\n",
    "        @cache\n",
    "        def solve(i, k):\n",
    "            if k == 1:\n",
    "                # print(i, k, 1)\n",
    "                return 1 if m - poss[i] >= minLength else 0\n",
    "            if n - i < k:\n",
    "                # print(i, k, 0)\n",
    "                return 0\n",
    "            ret = sum(solve(j, k - 1) for j in range(i + 1, n - k + 2) if poss[j] - poss[i] >= minLength) % 1000000007\n",
    "            # print(i, k, ret)\n",
    "            return ret\n",
    "        \n",
    "        return solve(0, kk)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        prime_index = [i for i in range(len(s)) if s[i] in '2357']\n",
    "        n, m = len(prime_index), len(s)\n",
    "        if len(prime_index) < k or prime_index[0] != 0:\n",
    "            return 0\n",
    "        @cache\n",
    "        def dfs(i: int, c: int) ->int:\n",
    "            l = prime_index[i]\n",
    "            if c == 0:\n",
    "                if m-l >= minLength and prime_index[-1] != m-1:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            cnt = 0\n",
    "            for j in range(i+1, n-c+1):\n",
    "                r = prime_index[j]\n",
    "                if r - l < minLength or prime_index[j-1] == r-1:\n",
    "                    continue\n",
    "                cnt += dfs(j, c-1)\n",
    "            return cnt%MOD\n",
    "        return dfs(0, k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        def is_prime(x):\n",
    "            return x in '2357'\n",
    "        if not is_prime(s[0]) or is_prime(s[-1]): return 0\n",
    "        n = len(s)\n",
    "        f = [[0] * (k+1) for _ in range(n+1)] # 对于方案数问题，非法状态的方案数就是0，不能初始为-inf\n",
    "        f[0][0] = 1\n",
    "        # f[i][j] += f[u][j-1], if s[u]为质数且s[i-1]为非质数且i-u>=minLength,u<i\n",
    "        # [0..i-1] = [0..u-1] + [u..i-1], if s[u]为质数且s[i-1]为非质数且i-u>=minLength,u<i\n",
    "        # for i in range(1, n+1):\n",
    "        #     for j in range(1, k+1):\n",
    "        #         for u in range(i): # u=0就是表示[0..u-1]为空串\n",
    "        #             if is_prime(s[u]) and not is_prime(s[i-1]) and i - u >= minLength:\n",
    "        #                 f[i][j] = (f[i][j] + f[u][j-1]) % MOD\n",
    "        # print(f)\n",
    "        # 前缀和优化\n",
    "        # i,j的枚举顺序是任意的\n",
    "        pre = [[0] * (k+1) for _ in range(n+1)]\n",
    "        pre[0][0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            if not is_prime(s[i-1]) and i - minLength >= 0 and (i == n or is_prime(s[i])):\n",
    "                for j in range(1, k+1):\n",
    "                    # 因为是前缀和pre[i-minLength]表示[0..i-minLength-1]分成j-1段的所有合法方案数，就不必枚举u了\n",
    "                    f[i][j] = (f[i][j] + pre[i-minLength][j-1]) % MOD \n",
    "            for j in range(k+1):\n",
    "                pre[i][j] = (pre[i-1][j] + f[i][j]) % MOD\n",
    "        return f[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        mod=10**9+7\n",
    "        n=len(s)\n",
    "        \n",
    "        \n",
    "        dp=[[0]*(k+1) for i in range(n)]\n",
    "        \n",
    "        sett=set()\n",
    "        sett.add('2')\n",
    "        sett.add('3')\n",
    "        sett.add('5')\n",
    "        sett.add('7')\n",
    "        \n",
    "        \n",
    "        presum=[[0]*(k+1) for i in range(n)]\n",
    "        \n",
    "        \n",
    "        \n",
    "        for i in range(n):\n",
    "            if s[0] in sett and s[i] not in sett and i>=minLength-1:\n",
    "                dp[i][1]=1\n",
    "            \n",
    "            for j in range(2,k+1):\n",
    "                \n",
    "                if i-minLength<0:continue\n",
    "                dp[i][j]=presum[i-minLength][j-1]\n",
    "                \n",
    "                dp[i][j]%=mod\n",
    "                \n",
    "                \n",
    "            \n",
    "            for j in range(k+1):\n",
    "                if not i:break\n",
    "                if i==n-1:break\n",
    "                presum[i][j]=(dp[i][j] if (s[i] not in sett and s[i+1] in sett) else 0)+presum[i-1][j]\n",
    "                presum[i][j]%=mod\n",
    "            \n",
    "        \n",
    "        return dp[-1][k]%mod\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        pres = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        for i in range(n + 1):\n",
    "            pres[i][0] = 1\n",
    "        if s[0] not in '2357':\n",
    "            return 0\n",
    "        def can_f(i):\n",
    "            if s[i - 1] not in '2357' and (i == len(s) or s[i] in '2357'):\n",
    "                return True\n",
    "            return False\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                if i >= minLength and can_f(i):\n",
    "                    dp[i][j] = pres[i - minLength][j - 1]\n",
    "            for j in range(1, k + 1):\n",
    "                pres[i][j] = pres[i - 1][j] + dp[i][j]\n",
    "        \n",
    "        return dp[n][k] % mod\n",
    "                \n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        dp = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        pres = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        pres[0][0] = 1\n",
    "        if s[0] not in '2357':\n",
    "            return 0\n",
    "        def can_f(i):\n",
    "            if s[i - 1] not in '2357' and (i == len(s) or s[i] in '2357'):\n",
    "                return True\n",
    "            return False\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                if i >= minLength and can_f(i):\n",
    "                    dp[i][j] = pres[i - minLength][j - 1]\n",
    "            for j in range(k + 1):\n",
    "                pres[i][j] = pres[i - 1][j] + dp[i][j]\n",
    "        \n",
    "        return dp[n][k] % mod\n",
    "                \n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        n = len(s)\n",
    "        arr = [0] * n\n",
    "        MOD = 10**9 + 7\n",
    "        for i, x in enumerate(s):\n",
    "            if x == '2' or x == '3' or x == '5' or x == '7':\n",
    "                arr[i] = 1\n",
    "        if not arr[0]: return 0\n",
    "        f = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        g = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = g[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            if i >= minLength and not arr[i - 1] and (i == n or arr[i]):\n",
    "                for j in range(1, k + 1):\n",
    "                    f[i][j] = g[i - minLength][j - 1]\n",
    "            for j in range(k + 1):\n",
    "                g[i][j] = g[i - 1][j] + f[i][j]\n",
    "        return f[n][k] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        if s[-1] in '2357':\n",
    "            return 0\n",
    "        n, mod = len(s), 10 ** 9 + 7\n",
    "        @lru_cache(None)\n",
    "        def dp(index, m):\n",
    "            if index + minLength > n or not s[index] in '2357':\n",
    "                return 0\n",
    "            if m == 1:\n",
    "                return 1\n",
    "            return sum(dp(i+1, m-1) for i in range(index + minLength - 1, n - (m-1) * minLength + 1) if not s[i] in '2357') % mod\n",
    "        return dp(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        if s[0] not in '2357':\n",
    "            return 0\n",
    "        MOD = 1e9 + 7\n",
    "        n = len(s)\n",
    "        f = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        g = [[0] * (k + 1) for _ in range(n + 1)]\n",
    "        f[0][0], g[0][0] = 1, 1\n",
    "        for i in range(1, n + 1):\n",
    "            if i >= minLength and s[i - 1] not in '2357' and (i == n or s[i] in '2357'):\n",
    "                for j in range(1, k + 1):\n",
    "                    f[i][j] = g[i - minLength][j - 1]\n",
    "            for j in range(k + 1):\n",
    "                g[i][j] = (g[i - 1][j] + f[i][j]) % MOD\n",
    "        return int(f[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:\n",
    "        zhi, he = set('14689'), set('2357')\n",
    "        if s[0] in zhi or s[-1] in he: return 0\n",
    "        @cache\n",
    "        def dfs(p: int, q: int) -> int:\n",
    "            if s[p] in zhi: return 0\n",
    "            if q == 1: return s[p] in he and len(s)-p>=minLength\n",
    "            res = 0\n",
    "            for cnt, i in enumerate(s[p+minLength-1: len(s)-(q-1)*minLength], p+minLength-1):\n",
    "                if i in zhi: res += dfs(cnt+1, q-1)\n",
    "            return res \n",
    "        return dfs(0, k) % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautifulPartitions(self, s: str, kk: int, minLength: int) -> int:\n",
    "        if s[0] not in '2357' or s[-1] in '2357':\n",
    "            return 0\n",
    "        \n",
    "        m = len(s)\n",
    "        poss = [0]\n",
    "        for i in range(1, m):\n",
    "            if s[i] in '2357' and s[i-1] not in '2357':\n",
    "                poss.append(i)\n",
    "\n",
    "        # print(poss)\n",
    "\n",
    "        n = len(poss)\n",
    "\n",
    "        @cache\n",
    "        def solve(i, k):\n",
    "            if k == 1:\n",
    "                # print(i, k, 1)\n",
    "                return 1 if m - poss[i] >= minLength else 0\n",
    "            if n - i < k:\n",
    "                # print(i, k, 0)\n",
    "                return 0\n",
    "            ret = sum(solve(j, k - 1) for j in range(i + 1, n) if poss[j] - poss[i] >= minLength) % 1000000007\n",
    "            # print(i, k, ret)\n",
    "            return ret\n",
    "        \n",
    "        return solve(0, kk)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
